package com.major.dawn.leetCode;

public class Search {


    public int search(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return -1;
        }

        if (length == 1) {
            if (nums[0] == target) {
                return 0;
            } else {
                return -1;
            }
        }

        //        定义区间的上限和下限
        int startIndex = 0;
        int endIndex = length - 1;
        int middleIndex = length / 2;

        return partitionNums(nums, target, startIndex, endIndex, middleIndex);
    }

    private int partitionNums(int[] nums, int target, int startIndex, int endIndex, int middleIndex) {


        if (nums[middleIndex] == target) {
            return middleIndex;
        }
        if (startIndex == middleIndex) {
            if (nums[endIndex] == target) {
                return endIndex;
            }
        }
        if (endIndex == middleIndex) {
            if (nums[startIndex] == target) {
                return startIndex;
            }
        }
        if (nums[middleIndex] < target) {
            middleIndex = (endIndex - middleIndex) / 2 + middleIndex;
            return partitionNums(nums, target, middleIndex + 1, endIndex,middleIndex);
        }

        if (nums[middleIndex] > target) {
            middleIndex = middleIndex - (middleIndex - startIndex) / 2;
            return partitionNums(nums, target, middleIndex + 1, endIndex,middleIndex);
        }

        return -1;
    }


    public int searchLeetcode(int[] nums, int target) {
        int pivot, left = 0, right = nums.length - 1;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            if (nums[pivot] == target) {
                return pivot;
            }

            if (target < nums[pivot]) {
                right = pivot - 1;
            } else{
                left = pivot + 1;
            }
        }
        return -1;
    }




    public static void main(String[] args) {
        Search search = new Search();
        int search1 = search.search(new int[]{-1, 0, 3, 5, 9, 12}, 9);
        System.out.println(search1);
    }

}
